The present invention relates to computer assisted design (CAD) tools used in designing synchronous logic, such as microprocessors. More particularly, the present invention relates to methods by which CAD tools such as timing analyzers determine the propagation delay of gates in synchronous designs.
During the development of synchronous machines, various designs are proposed and modified. Each design is tested for bugs and for performance (i.e., speed) and modified accordingly to remove bugs and improve performance. Ultimately, a design is deemed sufficiently bug-free and fast to be frozen and converted to hardware.
Each design considered in this process consists of stages which are delimited by clocked elements. The clocked elements are connected to other clocked elements by various paths consisting of at least a wire and potentially many wires and gates. The design's speed can be determined by predicting the delay between any two stages in the processor design with a tool known as a static timing analyzer. Typically, in current microprocessor designs, the delay between stages is on the order of nanoseconds.
FIG. 1 shows a hypothetical representative section 2 of a microprocessor design in a synchronous computer. Section 2 may be a part of a device layout proposed during the development of a microprocessor design. The microprocessor has clocked elements 4, 6, and 8 among many others not shown. Most typically, a clocked element is a flip-flop, latch, a register or memory. Between clocked elements 6 and 8, there are a series of gates 30, 32, 36, and 38 and branches 10 and 14 which connect with other clocked elements (not shown) in the system.
By determining the slowest path between each two successive clocked elements, the speed of the processor design can be determined. Static timing analyzers do this by a data invariant determination of the slowest path between each two successive clocked elements. For example, in the section shown in FIG. 1, a static timing analyzer will begin at clocked element 6, determine the delay between that element and the first gate it encounters, gate 30, and then determine the delay between gate 30 and the next gate on its path, gate 32. At this point, a branch 10 is reached, and the static timing analyzer must determine which path to take. In order to give a conservative estimate of speed, the timing analyzer always takes the path that will require most time to traverse. Determining which branch meets this requirement may be accomplished by any of several algorithms used in the commercial tools. The simplest one (more efficiency is possible) is a two pass computation which determines the delay to every node and then sorts for the longest delays to the clocked elements. In this manner, the timing analyzer can determine which path between any two timing elements is slowest, and how much time it takes to traverse that path. By combining these times, the overall speed of the processor design is determined.
The amount of time required to traverse any path on a typical microprocessor is often governed by the propagation delay of each gate on that path. The propagation delay (sometimes referred to as propagation time) is the amount of time required by a gate to switch states in response to a signal change on its input pin. A very accurate value of the propagation delay can be obtained by modeling the transistors included in the gate and numerically solving the differential equations describing these transistors. Various numerical routines such as SPICE (available from the University of California, Berkeley) are available for making such accurate determinations. While the accuracy of these products is unquestioned, they are computationally expensive and therefore unsuitable for use in a static timing analyzer which must typically determine the propagation delay of at least one hundred thousand different gates.
Thus, prior static timing analyzers have approximated the propagation delay by computationally simple techniques as illustrated in FIG. 2. The actual propagation delay of a gate is a function of the load on that gate (among other variables) as shown by the curve labeled "Actual" in FIG. 2. Early static timing analyzers approximated actual propagation delay as a linear function of the load on a gate, as shown in the line labeled "Linear Model" in FIG. 2. Unfortunately, this approximation is quite inaccurate for large fractions of the curve, especially in smaller devices. This led some in the field to approximate propagation delay as a series of lines connected by "breakpoints" as shown as the multi-part curve labeled "Breakpoint Model" in FIG. 2. While representing an improvement, the Breakpoint Model was found to be insufficient for many applications. This led some researchers to look for a continuous mathematical expression that would describe the "actual" relationship between gate load and propagation delay, and efforts in this area continue today. Ultimately, however, some in the field concluded that even this approach was never going to prove sufficiently accurate because the propagation delay of a gate is actually a function of both input "rise time" and load. The input rise time of a gate is the time required (typically on the order of a few hundred picoseconds up to nanoseconds) for an input voltage signal to that gate to switch from low to high or high to low, whichever direction is appropriate. This is a function of the output switching time of a gate immediately preceding the gate under consideration in a path within the network and, potentially, the wire between these gates. Because propagation delay is a function of both input rise time and load, it can be represented as a three dimensional surface (such as that shown in FIG. 6 and discussed below) having a projection on a plane defined by a load "axis" and an input rise time "axis."
One static timing tool, which is incorporated in the product "Design Compiler".RTM. available from Synopsys, Inc., Mountain View, Calif., does in fact treat propagation delay as a surface which is a function of input rise time and gate load. Design Compiler.RTM. provides a lookup table having grid points defined by combinations of load and input rise time. For each such grid point, a propagation time is provided which was previously determined by a numerical analysis of the transistors making up a gate, and using the input rise time and load as specified by the grid point. When Design Compiler.RTM. is presented with a gate, it first determines the input rise time and load associated with that gate. It then finds a "subsurface" within which the gate's load and input rise time resides. This subsurface is defined by four grid points having adjacent values of load and input rise time. Design Compiler.RTM. then calculates a propagation delay of the gate under consideration by interpolating within the four grid points defining the appropriate subsurface. Design Compiler.RTM. uses the following widely-used "textbook" formula: EQU propagation delay=A+B(rise time)+C(gate load)+D(rise time)*(gate load)
where A, B, C, and D are coefficients determined from the coordinates of the four points defining the appropriate subsurface. The first three terms are linear and the fourth is non-linear. The coefficients are determined by writing an equation in this form for each of the four grid points which define the subsurface. For each equation, the propagation delay, input rise time, and gate load are known, and the coefficients A, B, C, and D are the variables. The resulting system of four linear simultaneous equations is solved for A, B, C, and D. With the values of A, B, C, and D known, the original formula may now be used to find the propagation delay for the actual input rise time and gate load.
Unfortunately, it has been found that the approach used by Design Compiler.RTM. provides somewhat inaccurate results, particularly in the regions where input rise time is relatively large (i.e., slow switching) and gate load is relatively small. Thus, for static timing analyzers there exists a need for a more accurate method of predicting the propagation delay of a gate.